1. Field of the Invention
The present invention relates to a technique for extracting at high speed all of boundaries (vertex boundary lines of pixel boundaries) between different color regions in a predetermined order, from a multivalued image.
2. Description of the Related Art
Techniques related to image vectorization originated from character-related techniques. Since then, a method for contour information extraction (U.S. Pat. No. 6,404,921) and a method for coordinate point sequence function approximation (U.S. Pat. No. 7,873,218) have been proposed. With the increase in the use of vectorization for ordinary illustration images, techniques for applying vectorization processing to diverse types of images, for example, a technique for line image vectorization (U.S. Pat. No. 7,889,938) and a technique for color image vectorization (U.S. Pat. No. 7,623,712) have been proposed.
Vectorized data enables smooth contour expression free from jaggy even after magnification to a desired size. Converting an illustration image having a small number of colors into vector data provides an effect of reduced data size and an advantage of facilitated editing processing by a computer.
Many of characters and line images can be handled as a binary image or a monochrome image (an image in which characters and lines are monochrome and other portions are white (background color)). With such an image, applying function approximation to contours (contours of a character and a line image) extracted for each color-connected region enables obtaining a desirable result of vectorization. A color-connected region (color region) refers to a region composed of connected pixels determined to have an identical color (a region in which pixels having an identical color are connected). On the other hand, many illustration images include more than two colors, causing a problem of handling a boundary line between a plurality of color regions. For example, similar to processing with a binary image, applying function approximation to the contour of each color region detected from a multi-color image enables individually approximating the contour of each of adjacent color regions. In this case, there has been a problem that two different approximated curves are obtained by an approximation error at a common boundary layer portion between adjacent color regions causing gaps and overlaps. Examples of gaps and overlaps are illustrated in FIGS. 3A and 3B. FIG. 3A illustrates exemplary contour shapes of respective color regions extracted from an input image. Assuming that the background white region is not counted, there are three different color regions adjacently existing to other color regions (having boundary lines with other regions). FIG. 3B illustrates a result of applying function approximation to contour information illustrated in FIG. 3A for each individual color region. In this case, gaps and overlaps are produced between color regions.
In consideration of the above-described problem, a vectorization method which does not produce a gap between color regions has been proposed. Japanese Patent Application Laid-Open No. 2006-031245 discusses a technique for tracing as a contour a boundary between pixels having at least a certain color difference, branching the processing each time an intersection of color regions (hereinafter referred to as a color intersection point) is encountered, and repeating a search. Since this technique applies function approximation processing to each partial contour sectioned by color intersection points, and reconnects data that has undergone function approximation to generate vector data of each color region, a common result of function approximation is applied to boundary lines. Therefore, theoretically, neither gap nor overlap arises.
As described in Toriwaki, “Digital Image Processing for Image Understanding (2)”, first edition, third printing, ISBN4-7856-2004-8, Shokodo, published on Apr. 20, 1993, pp. 66-79, a boundary line between color regions is extracted by tracing a boundary line between color regions. When each of different color regions is considered as graphics, a boundary line refers to a set of boundaries between a point inside the graphics and a point outside the graphics. As described on page 68 in Toriwaki, “Digital Image Processing for Image Understanding (2)”, known boundary line tracing methods are classified into three types: pixel tracing type, edge tracing type, and vertex tracing type. The following descriptions will be made focusing on the vertex tracing type with which a gapless common contour line is defined between adjacent color regions in an image. As a boundary line tracing method of the vertex tracing type, a boundary line tracing method discussed in Japanese Patent Application Laid-Open No. 2006-031245 is known. The boundary line tracing method of this type searches for a search starting point of color regions subjected to extraction, and then traces color boundaries while determining a color region on the right-hand side or left-hand side as a color region subjected to extraction. When a color intersection point is encountered, the method records boundary lines which have been extracted until then and then starts new extraction. The method repeats the above-described processing for tracing color boundaries in this way until all of boundary lines have been extracted.
This method has some problems. First of all, there are some search orders when a color intersection point is encountered (when there is a plurality of search orders, which order is given priority is a problem). Depending on a method for selecting the order of extraction, reconstructing a contour by arranging boundary lines may become difficult, or a boundary line extraction failure may easily occur. Further, since the tracing direction changes by the region shape, there may be a case where memory cache does not work when referring to pixel information in memory, possibly resulting in processing speed reduction.